package problem132_Palindrome_Partitioning_II;

public class Solution {
	 public int minCut(String s) {
		 char[] input=s.toCharArray();
		 int[] minCut=new int[input.length];
		 boolean[][] isPalindrome=new boolean[input.length][input.length];
		 for(int i=0;i<input.length;i++){
			 minCut[i]=i;
			 for(int j=0;j<=i;j++){
				 if(input[j]==input[i]&&(i-j<=1||isPalindrome[j+1][i-1])){
					 isPalindrome[j][i]=true;
					 if(j==0){
						 minCut[i]=0;
					 }else{
						 minCut[i]=Math.min(minCut[i], minCut[j-1]+1);
					 }
				 }
			 }
		 }
		 return minCut[minCut.length-1];
	 }
}
